package com.fanwh.tree.Order;

/**
 * @program: DataStructure
 * @description: 二叉树排序
 * @author: Fanwh
 * @create: 2020-09-28 14:12
 **/
public class BinaryTreeOrder {

    public static void main(String[] args) {

        //创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建树节点
        TreeNode root = new TreeNode(1,"范伟红");
        TreeNode node2 = new TreeNode(2,"吴佳骏");
        TreeNode node3 = new TreeNode(3,"许慧鑫");
        TreeNode node4 = new TreeNode(4,"张超伟");
        TreeNode node5 = new TreeNode(5,"龙");

        //手动定义二叉树的关系
        binaryTree.setRoot(root);
        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node5);
        node3.setRight(node4);

        //测试
        System.out.println("前序遍历");
        binaryTree.preOrder();//1,2,3,5,4

        //测试
        System.out.println("中序遍历");
        binaryTree.midOrder();//2,1,5,3,4

        //测试
        System.out.println("后序遍历");
        binaryTree.postOrder();//2,5,4,3,1

        //遍历查找
        System.out.println("前序遍历方式");
        TreeNode resnode1 = binaryTree.preOrderSearch(5);
        if(resnode1 != null){
            System.out.printf("找到num = %d的信息,name = %s",resnode1.getNum(),resnode1.getName());
            System.out.println();
        }else {
            System.out.printf("没有找到 num = %d的信息",5);
        }

        System.out.println("中序遍历方式");
        TreeNode resnode2 = binaryTree.midOrderSearch(5);
        if(resnode2 != null){
            System.out.printf("找到num = %d的信息,name = %s",resnode2.getNum(),resnode2.getName());
        }else {
            System.out.printf("没有找到 num = %d的信息",5);
        }
        System.out.println();
        System.out.println("后序遍历方式");
        TreeNode resnode3 = binaryTree.postOrderSearch(5);
        if(resnode3 != null){
            System.out.printf("找到num = %d的信息,name = %s",resnode3.getNum(),resnode3.getName());
        }else {
            System.out.printf("没有找到 num = %d的信息",5);
        }
    }
}

//定义一颗二叉树
class BinaryTree{
    private TreeNode root;//根节点

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //调用遍历方法
    //前序遍历
    public void preOrder(){
        if (this.root != null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //中序遍历
    public void midOrder(){
        if (this.root != null){
            this.root.midOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //后序遍历
    public void postOrder(){
        if(this.root != null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //调用遍历查找方法
    //前序遍历查找
    public TreeNode preOrderSearch(int num){
        if (this.root != null){
            return root.preOrderSearch(num);
        }else {
            return null;
        }
    }

    //中序遍历查找
    public TreeNode midOrderSearch(int num){
        if (this.root != null){
            return root.midOrderSearch(num);
        }else {
            return null;
        }
    }
    //后序遍历查找
    public TreeNode postOrderSearch(int num){
        if (this.root != null){
            return root.postOrderSearch(num);
        }else {
            return null;
        }
    }
}

//定义树节点并给出前、中、后序遍历的具体方法
class TreeNode{
    private int num;
    private String name;
    private TreeNode left;//默认为null
    private TreeNode right;//默认为null

    public TreeNode(int num,String name){
        this.name = name;
        this.num = num;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public int getNum() {
        return num;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode [num="+num+",name="+name+"]";
    }

    /**前序遍历
     * 1.首先输出当前节点(初始的时候是root结点)
     * 2.如果当前节点的左节点不为空，则递归前序遍历
     * 3.如果当前节点的右节点不为空，则递归继续前序遍历
     */
    public void preOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.preOrder();
        }
        if(this.right != null){
            this.right.preOrder();
        }
    }

    /**中序遍历
     * 1.如果当前节点的左节点不为空，则递归中序遍历
     * 2.输出当前节点
     * 3.如果当前节点的右节点不为空，则递归中序遍历
     */
    public void midOrder(){
        if(this.left != null){
            this.left.midOrder();
        }
        System.out.println(this);
        if(this.right != null){
            this.right.midOrder();
        }
    }

    /**后序遍历
     * 1.如果当前节点的左节点不为空，则递归后序遍历
     * 2.如果当前节点的右节点不为空，则递归后序遍历
     * 3.输出当前节点
     */
    public void postOrder(){
        if(this.left != null){
            this.left.postOrder();
        }
        if (this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

    /**
     * @Description: 前、中、后序遍历查找
     * @Param: [num]
     * @return: 找到对应编号的节点，就返回该节点；否则返回null
     * @Author: Fanwh
     * @Date: 2020/9/28
     */
    public TreeNode preOrderSearch(int num){
        System.out.println("进入前序遍历");
        if(this.num == num){
            return this;
        }
        TreeNode resNode = null;//返回节点

        //如果当前节点的编号与给定编号不一致，则判断当前节点的左子节点是否为空
        //如果不为空，则继续前序遍历查找
        if(this.left != null){
            resNode = this.left.preOrderSearch(num);
        }
        if(resNode != null){//在左子树找到对应节点
            return resNode;
        }
        //如果左子节点也没找到，则前序遍历查找右子节点
        if (this.right != null){
            resNode = this.right.preOrderSearch(num);
        }
        return resNode;
    }

    public TreeNode midOrderSearch(int num){

        TreeNode resNode = null;
        //首先判断当前节点的左子节点是否为空,如果不为空，则中序遍历查找左子节点
        if (this.left != null){
            resNode = this.left.midOrderSearch(num);
        }
        if(resNode != null){//在左子树找到对应节点
            return resNode;
        }
        //如果左子节点中没有找到，匹配当前节点是否一致
        System.out.println("进入中序遍历");
        if (this.num == num ){
            return this;
        }
        //如果当前节点也不匹配，中序遍历查找右子节点
        if (this.right != null){
            resNode = this.right.midOrderSearch(num);
        }

        return resNode;
    }

    public TreeNode postOrderSearch(int num){

        TreeNode resNode  = null;
        //首先，判断当前节点的左子节点是否为空
        //如果不为空，则后序遍历查找左子节点
        if (this.left != null){
            resNode = this.left.postOrderSearch(num);
        }
        if(resNode != null){//在左子树找到对应节点
            return resNode;
        }
        //如果左子节点中没有找到，则判断当前的节点的右子节点是否为空
        //如果不为空，则后序遍历查找右子节点
        if (this.right != null ){
            resNode = this.right.postOrderSearch(num);
        }
        if(resNode != null){//在右子树找到对应节点
            return resNode;
        }
        //左右子树都没有找到对应节点，匹配当前节点是否一致
        System.out.println("进入后序遍历");
        if (this.num == num){
            return this;
        }
        return resNode;
    }
    /**
     * @Description: 删除对应节点编号的节点
     * @Param: [num]
     * @return: void
     * @Author: Fanwh
     * @Date: 2020/9/28
     */
    public void delTreeNode(int num){

        /**思路
         * 1、判断当前节点的左子节点是否为空并且该左子节点的编号是否与要删除一致，如果一致，
         *      则让this.left = null,并结束删除方法
         * 2、判断当前节点的右子节点是否为空并且该右子节点的编号是否与要删除一致，如果一致，
         *      则让this.left = null,并结束删除方法
         */
        if (this.left != null && this.left.num == num){
               this.left = null;
               return;
        }
        if (this.right != null && this.right.num == num){
               this.right = null;
               return;
        }
    }
}